package baseclass.m_graph;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * 	DFS类似树的先序遍历的思想。任意遍历到一个节点，
 * 	如果节点有邻居，则访问邻居 ，递归次过程。
 * @date 2020/3/6 20:19
 */
public class Code2_DFS {
    //递归版
    public static void dfs1(Node node,Set<Node> set){
        System.out.print(node.val+"->");
        set.add(node);
        for (Node next : node.nexts) {
            if(!set.contains(next)){
                dfs1(next,set);
            }
        }
    }
    //非递归版
    public static void dfs2(Node node){
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        Set<Node> set = new HashSet<>();
        stack.push(node);
        set.add(node);
        System.out.print(node.val+"->");

        while (!stack.isEmpty()){
            //出栈栈顶节点
            Node cur = stack.pop();
            //访问
            //遍历所有邻居，只要有一个没有访问过则先入栈自己，再入栈邻居
            for (Node next : cur.nexts) {
                if(!set.contains(next)){
                    stack.push(cur);
                    stack.push(next);
                    set.add(next);
                    //一入栈则打印，下次入栈不会以next身份 ，最多会以cur的身份
                    System.out.print(next.val+"->");
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        Integer[][]matrix = {{-1,1,2},{-1,1,3},{-1,2,3},{-1,1,4},{-1,2,7},{-1,7,3},{-1,
                3,5},{-1,4,6}};
        Graph graph = Graph.createGraph(matrix);
        dfs1(graph.nodes.get(1),new HashSet<>());
        System.out.println("===");
        dfs2(graph.nodes.get(1));
    }

}
